      1  import java.util.ArrayList;

      2

      3  /**

      4     A maze has its walls marked by * characters and corridors

      5     by spaces. It can classify corridor points as dead ends,

      6     intersections, or exits, and it can extend paths from

      7     one intersection to another. The maze is assumed not to have

      8     any cycles (i.e., paths returning to their own start.)

      9  */

     10  public class Maze

     11  {

     12     private String[] cells;

     13

     14     /**

     15        Constructs a maze from a string describing its contents.

     16        @param contents strings consisting of * and spaces

     17     */

     18     public Maze(String[] contents)

     19     {

     20        cells = contents;

     21     }

     22

     23     /**

     24        Gets all paths emanating from a position in the maze.

     25        @param row the row of the position

     26        @param column the column of the position

     27        @return all paths emanating from the position

     28     */

     29     public ArrayList<Path> pathsFrom(int row, int column)

     30     {

     31        ArrayList<Path> paths = new ArrayList<Path>();

     32        if (isValid(row - 1, column))

     33        {

     34           paths.add(new Path(row, column, Path.NORTH));

     35        }

     36        if (isValid(row, column + 1))

     37        {

     38           paths.add(new Path(row, column, Path.EAST));

     39        }

     40        if (isValid(row + 1, column))

     41        {

     42           paths.add(new Path(row, column, Path.SOUTH));

     43        }

     44        if (isValid(row, column - 1))

     45        {

     46           paths.add(new Path(row, column, Path.WEST));

     47        }

     48        for (Path p : paths) { extend(p); }

     49        return paths;

     50     }

     51

     52     /**

     53        Extends this path to the next exit, intersection, or dead end.

     54        @param p the path to extend

     55     */

     56     private void extend(Path p)

     57     {

     58        boolean done = false;

     59        while (!done)

     60        {

     61           p.move();

     62           int row = p.getEndingRow();

     63           int column = p.getEndingColumn();

     64           if (isExit(row, column) || countNeighbors(row, column) != 2)

     65           {

     66              done = true; // Either a straight path or a turn

     67           }

     68           else

     69           {

     70              row = p.getNextRow();

     71              column = p.getNextColumn();

     72              if (!isValid(row, column))

     73              {

     74                 p.turn();

     75                 row = p.getNextRow();

     76                 column = p.getNextColumn();

     77                 if (!isValid(row, column))

     78                 {

     79                    p.turn();

     80                    p.turn();

     81                 }

     82              }

     83           }

     84        }

     85     }

     86

     87     /**

     88        Checks whether a position is an exit.

     89        @param row the row of the position

     90        @param column the column of the position

     91        @return true if the position is an exit

     92     */

     93     public boolean isExit(int row, int column)

     94     {

     95        return (row == 0 || row == cells.length - 1

     96           || column == 0 || column == cells[row].length() - 1)

     97           && cells[row].charAt(column) == ' ';

     98     }

     99

    100     /**

    101        Checks whether a position is a dead end.

    102        @param row the row of the position

    103        @param column the column of the position

    104        @return true if the position is a dead end

    105     */

    106     public boolean isDeadEnd(int row, int column)

    107     {

    108        return countNeighbors(row, column) == 1;

    109     }

    110

    111     /**

    112        Checks whether a position is within the maze and not a wall.

    113        @param row the row of the position

    114        @param column the column of the position

    115        @return true if the position is valid

    116     */

    117     private boolean isValid(int row, int column)

    118     {

    119        return 0 <= row && row < cells.length

    120           && 0 <= column && column < cells[row].length()

    121           && cells[row].charAt(column) == ' ';

    122     }

    123

    124     /**

    125        Counts the neighbors of a position.

    126        @param row the row of the position

    127        @param column the column of the position

    128        @return the number of neighbors in the four compass directions

    129        that are within the maze and not walls.

    130     */

    131     private int countNeighbors(int row, int column)

    132     {

    133        int count = 0;

    134        if (isValid(row - 1, column)) { count++; }

    135        if (isValid(row + 1, column)) { count++; }

    136        if (isValid(row, column - 1)) { count++; }

    137        if (isValid(row, column + 1)) { count++; }

    138        return count;

    139     }

    140  }